#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include<numeric>
using namespace std;

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
       //采用二分法
       //设ans为最低的运载重量，[-无穷，ans)区间都不能满足，【ans,+无穷）都能满足
        //ans的范围为[maxweight,sum]
        int maxweight = 0;
        int sum = 0;
        for(int weight:weights){
            maxweight = max(maxweight,weight);
            sum+=weight;
        }
        int left = maxweight;
        int right = sum;
        while(left<right){
            int mid = (left+right)/2;
            if(func(weights,mid,D)){
                right = mid;
            }
            else{
                left = mid+1;
            }
        }
        return left;

    }
    //检测mid是在ans的左边还是在ans的右边
    bool func(vector<int>& weight,int mid,int D){
        int sum = 0;
        int day = 1;
        for(int i = 0;i<weight.size();++i){
            sum+=weight[i];
            if(sum>mid){
                sum = weight[i];
                ++day;
            }
        }
        return day>D? false:true;
    }
};

int main(){
    Solution S;
    vector<int> weight = {1,2,3,4,5,6,7,8,9,10};
    cout<<S.shipWithinDays(weight,5)<<endl;
}